The present invention relates generally to image processing, and more particularly to multilevel image segmentation.
Digital image processing is becoming increasingly popular as digital imaging devices continue to become more powerful. For example, digital cameras can generate pictures having 10 million pixels, and Computed Tomography (CT) scanners may produce volume data having more than 100 million voxels. Processing these images places a large computational burden on the various devices that perform image processing.
One type of processing that is often performed on image data is segmentation, whereby a boundary is determined between different portions of the image. For example, in digital photography, it is often desirable to define a boundary between a main object and background, in order to segment out the main object. After the main object is segmented, the main object and background may be processed separately. Similarly, in the medical imaging field, it is often desirable to segment out a particular object, or portion of an object, from a CT scan image. For example, in the case of a CT scan of a human heart, it may be desirable to segment out a portion of the heart (e.g., left atrium) in order to allow a physician to more easily analyze the image. One example of segmentation is illustrated in FIG. 1 which shows a rough image 100 of the left side of a human heart. Assume that the object of interest is the left atrium 102 with the remaining portion of the image not being of interest. A desirable segmentation is one which provides a boundary between the object of interest 102 and the remaining portion of the image. Such a boundary is shown in FIG. 1 as dotted line 104. Thus, an appropriate segmentation process would generate boundary 104 between the object of interest 102 and the remainder of the image.
One well know technique for image segmentation is the use of graph cuts, as described in Y. Boykov and M. Jolly, Interactive Graph Cuts for Optimal Boundary & Region Segmentation of Objects in N-D Images, Proceedings of International Conference on Computer Vision, Vol. 1, July 2001, Vancouver, Canada, pp 105-112. As will be described in further detail below, the graph cuts technique is an interactive segmentation technique that divides an image into two segments, an object and background. A user imposes constraints for the segmentation by indicating certain pixels that are part of the object and certain pixels that are part of the background. The image is then automatically segmented using graph cuts to find the globally optimal segmentation of the image.
The above identified graph cuts technique has become one of the leading algorithms for interactive image segmentation in 2 dimensions (2D) and 3 dimensions (3D). While this technique provides accurate results for low resolution images, it is of limited use for high resolution images due to its intense memory requirements and its supralinear time complexity. For example, to segment a typical CT volume of 5123 voxels in a medical imaging application, the memory consumption would be more than 8GB, which is impractical for current clinical computers. Further, in a worst case complexity scenario, such segmentation could require an extremely long processing time in order to complete, which is impractical for a medical imaging application.
Thus, what is needed is a computationally efficient segmentation technique that provides acceptable segmentation results.